Local-Search based Approximation Algorithms for Mobile Facility Location Problems

摘要

We consider the {\em mobile facility location} (\mfl) problem. We are given aset of facilities and clients located in a common metric space. The goal is tomove each facility from its initial location to a destination and assign eachclient to the destination of some facility so as to minimize the sum of themovement-costs of the facilities and the client-assignment costs. Thisabstracts facility-location settings where one has the flexibility of movingfacilities from their current locations to other destinations so as to serveclients more efficiently by reducing their assignment costs. We give the first {\em local-search based} approximation algorithm for thisproblem and achieve the best-known approximation guarantee. Our main result is$(3+\epsilon)$-approximation for this problem for any constant $\epsilon>0$using local search. The previous best guarantee was an 8-approximationalgorithm based on LP-rounding. Our guarantee {\em matches} the best-knownapproximation guarantee for the $k$-median problem. Since there is anapproximation-preserving reduction from the $k$-median problem to \mfl, anyimprovement of our result would imply an analogous improvement for the$k$-median problem. Furthermore, {\em our analysis is tight} (up to $o(1)$factors) since the tight example for the local-search based 3-approximationalgorithm for $k$-median can be easily adapted to show that our local-searchalgorithm has a tight approximation ratio of 3. One of the chief novelties ofthe analysis is that in order to generate a suitable collection of local-searchmoves whose resulting inequalities yield the desired bound on the cost of alocal-optimum, we define a tree-like structure that (loosely speaking)functions as a "recursion tree", using which we spawn off local-search moves byexploring this tree to a constant depth.